package com.study.lihan.letcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/*
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

如何存储数字对应的字母
使用递归
* */
public class My17 {
    static  String s  ="2";
    static  List<String> result  = new ArrayList<>();
    static  StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
      letterCombinations("23");
        System.out.println("结果是："+result);
    }

    public static List<String> myletterCombinations(String digits) {
        if(digits== null || digits.length()==0)return  new ArrayList<String>();
        Map<String,String> str4num = new HashMap<>();
        str4num.put("2","abc");
        str4num.put("3","def");
        str4num.put("4","ghi");
        str4num.put("5","jkl");
        str4num.put("6","mno");
        str4num.put("7","pqrs");
        str4num.put("8","tuv");
        str4num.put("9","wxyz");

        String firstNum = digits.substring(0,1);
        String firstStr = str4num.get(firstNum);
        List<String> dpList1 = new ArrayList<>(firstStr.length());
        for(int i =0; i<firstStr.length(); i++){
            dpList1.add(firstStr.substring(i,i+1));
        }
        for(int i = 1; i<digits.length(); i++){
            String nextNum = digits.substring(i,i+1);
            String nextStr = str4num.get(nextNum);
            int newSize = dpList1.size()* nextStr.length();
            List<String> dpList2 = new ArrayList<>(newSize);
            for(int j = 0; j< dpList1.size(); j++){
                for(int z=0;z<nextStr.length();z++){
                    dpList2.add(dpList1.get(j)+nextStr.substring(z,z+1));
                }

            }
            dpList1 = dpList2;
        }

        return dpList1;
    }
    public static  List<String> letterCombinations(String digits) {
        if(digits== null || digits.length()==0)return  new ArrayList<String>();
        Map<String,String> str4num = new HashMap<>();
        str4num.put("2","abc");
        str4num.put("3","def");
        str4num.put("4","ghi");
        str4num.put("5","jkl");
        str4num.put("6","mno");
        str4num.put("7","pqrs");
        str4num.put("8","tuv");
        str4num.put("9","wxyz");
        backTracing(str4num,digits,0);

       return result;
    }

    static void backTracing(Map<String,String> str4num,String digits, int  index){
        if(index== digits.length()){
            result.add(sb.toString());
            return;
        }

        String s = digits.substring(index,index+1);
        String letter = str4num.get(s);
        for(int i=0; i<letter.length(); i++){
            sb.append(letter.charAt(i));
            backTracing(str4num,digits,index+1);
            sb.deleteCharAt(sb.length()-1);
        }


    }
}
